"""
写一段代码，求出两个整数的最大公约数，要尽量优化算法的性能。
"""


def get_greatest_common_divisor_v1(a, b):
    """
    ”暴力枚举“
    从较小整数的一半开始，试图找到一个合适的整数 i，
    看看这个整数能否被a和b同时整除。
    :param a:
    :param b:
    :return:
    该方法虽然实现了所要求的功能，但是效率不行啊。
    想想看，如果传入的整数是10000和10001，用该方法就需要循环10000/2-1=4999次
    """
    big = max(a, b)
    small = min(a, b)
    if big % small == 0:
        return small
    for i in range(small // 2, 1, -1):
        if small % i == 0 and big % i == 0:
            return i
    return 1


"""
辗转相除法，又名欧几里得算法(Euclidean algorithm)，该算法的目的是求出两个正整数的最大公约数。
它是已知最古老的算法，其产生时间可追溯至公元前300年。


这条算法基于一个定理：
两个正整数 a 和 b(a > b)，它们的最大公约数等于 a 除以 b 的余数 c 和 b 之间的最大公约数。
例如，10和25，25除以10商2余5，那么10和25的最大公约数，等于10和5的最大公约数。


有了这条定理，求最大公约数就变得简单了。
我们可以使用 递归 的方法把问题逐步简化。
首先，计算出 a 除以 b 的余数 c，把问题转化成求 b 和 c 的最大公约数；
然后计算出 b 除以 c 的余数 d，把问题转化成求 c 和 d 的最大公约数；
再计算出 c 除以 d 的余数 e，把问题转化成求 d 和 e 的最大公约数……
以此类推，
逐渐把两个较大整数之间的运算简化成两个较小整数之间的运算，直到两个数可以整除，或者其中一个数减小到1为止。
"""


def get_greatest_common_divisor_v2(a, b):
    """
    当两个整数较大时，做 a % b 取模运算的性能会比较差。
    :param a:
    :param b:
    :return:
    """
    big = max(a, b)
    small = min(a, b)

    if big % small == 0:
        return small
    return get_greatest_common_divisor_v2(small, big % small)


"""
更相减损术，出自中国古代的《九章算术》，也是一种求最大公约数的算法。
古希腊人很聪明，可是我们炎黄子孙也不差。

它的原理更加简单：
两个正整数 a 和 b(a > b)，它们的最大公约数等于 a - b 的差值 c 和较小数 b 的最大公约数。
例如，10和25，25减10的差是15，那么10和25的最大公约数，等同于10和15的最大公约数。

由此，我们同样可以通过递归来简化问题。
首先，计算出a和b的差值c(假设a>b)，把问题转化成求b和c的最大公约数；
然后计算出c和b的差值d(假设c>b)，把问题转化成求b和d的最大公约数；
再计算出b和d的差值e(假设b>d)，
把问题转化成求d和e的最大公约数……
以此类推，逐渐把两个较大整数之间的运算简化成两个较小整数之间的运算，直到两个数相等为止，

最大公约数就是最终相等的这两个数的值。
"""


def get_greatest_common_divisor_v3(a, b):
    """
    更相减损术的过程就是这样的。我们避免了大整数取模可能出现的性能问题，已经越来越接近最优解决方案了。
    但是更相减损术是不稳定的算法，当两数相差悬殊时，如计算10000和1的最大公约数，就要递归9999次
    :param a:
    :param b:
    :return:
    """
    if a == b:
        return a
    big = max(a, b)
    small = min(a, b)
    return get_greatest_common_divisor_v3(small, big - small)


"""
最优方法：把辗转相除法和更相减损术的优势结合起来，在更相减损术的基础上使用移位运算。

众所周知，移位运算的性能非常好。对于给出的正整数 a 和 b，不难得到如下的结论：
(从下开始，获得最大公约数的方法get_greatest_common_divisor简写为gcd。)
    当a和b均为偶数时，
        gcd(a, b) = 2 × gcd(a / 2, b / 2) = 2 × gcd(a >> 1, b >> 1)。
    
    当a为偶数，b为奇数时，
        gcd(a, b) = gcd(a / 2, b) = gcd(a >> 1, b)。
    
    当a为奇数，b为偶数时，
        gcd(a, b) = gcd(a, b / 2) = gcd(a, b >> 1)。
    
    当a和b均为奇数时，先利用更相减损术运算一次，
        gcd(a, b) = gcd(b, a - b)，
    此时a - b必然是偶数，然后又可以继续进行移位运算。

例如，计算10和25的最大公约数的步骤如下：
    1.整数10通过移位，可以转换成求5和25的最大公约数。
    2.利用更相减损术，计算出25-5=20，转换成求5和20的最大公约数。
    3.整数20通过移位，可以转换成求5和10的最大公约数。
    4.整数10通过移位，可以转换成求5和5的最大公约数。
    5.利用更相减损术，因为两数相等，所以最大公约数是5。
    
这种方式在两数都比较小时，可能看不出计算次数的优势；当两数越大时，计算次数的减少就会越明显。
"""


def get_greatest_common_divisor_v4(a, b):
    if a == b:
        return a
    if a & 1 == 0 and b & 1 == 0:
        # a 和 b 为偶数
        # & 按位与：两位都为1,结果为1,否则为0
        #    0011 1100
        #    0000 1101
        # -> 0000 1100
        return get_greatest_common_divisor_v4(a >> 1, b >> 1) << 1
    elif a & 1 == 0 and b & 1 == 1:
        # a 为偶数, b 为奇数
        return get_greatest_common_divisor_v4(a >> 1, b)
    elif a & 1 == 1 and b & 1 == 0:
        # a 为奇数, b 为偶数
        return get_greatest_common_divisor_v4(a, b >> 1)
    else:
        # a 和 b 为奇数
        big = max(a, b)
        small = min(a, b)
        return get_greatest_common_divisor_v4(small, big - small)


if __name__ == '__main__':
    get_greatest_common_divisor_v2(1001, 1000)
    print(get_greatest_common_divisor_v3(99, 105))
    print(get_greatest_common_divisor_v4(99, 105))
    """
    1.暴力枚举法：时间复杂度是O（min（a，b））。
    2.辗转相除法：时间复杂度不太好计算，可以近似为O（log（max（a，b））），但是取模运算性能较差。
    3.更相减损术：避免了取模运算，但是算法性能不稳定，最坏时间复杂度为O（max（a，b））。
    4.更相减损术与移位相结合：不但避免了取模运算，而且算法性能稳定，时间复杂度为O（log（max（a，b）））。
    """
